package code2;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 8:58
 *
 * 二分查找变种3：
 * 如果数组中存在元素target，则返回最小索引
 * 如果数组中不存在元素，返回 Upper【比目标值小的最小值的索引】
 *  根据upper改写
 */
public class BinarySearchLowerCeil {

//    lower_ceil本质就是>=target 返回最小索引
    // >=target 返回最小索引
    public static <E extends Comparable<E>> int lowerCeil(E[] data,E target){
        int left = 0;
        int right = data.length;

        while (left < right){
            int mid = left + (right - left)/2;

            if(data[mid].compareTo(target) < 0){  //upper <=0
                left = mid + 1;

//所以在等于的情况下，不能排除掉data[mid] 的值。在等于的情况下，应该归入下面的else中做处理
//也就是，data[mid] == target 的时候可能是解，也可能有更小的解在左边，应该去更新右边界
            }else  if(data[mid].compareTo(target) >= 0){ //upper中 >0
                right = mid;
            }
        }

        //当left==right就是循环停止的条件
        return left; //返回right也是一样的


    }

    public static void main(String[] args) {
        Integer[] arr = {1,1,3,3,5,5};
        for (int i = 0; i <= 6 ; i++) {
            int search = BinarySearchLowerCeil.lowerCeil(arr, i);
            System.out.println( "求target="+i +"的ceil的索引为:"+search + " ");
        }
        System.out.println();
    }

}
